Sự phân tích duy nhất

Viết một số thành tích của các số nguyên tố được gọi là phân tích nguyên tố của số đó. Chẳng hạn:

34866 = 2 ⋅ 3 ⋅ 3 ⋅ 13 ⋅ 149 = 2 ⋅ 3 2 ⋅ 13 ⋅ 149. {\displaystyle {\begin{aligned}34866&=2\cdot 3\cdot 3\cdot 13\cdot 149\\&=2\cdot 3^{2}\cdot 13\cdot 149.\end{aligned}}}

Các thừa số trong tích được gọi là thừa số nguyên tố. Một thừa số nguyên tố có thể xuất hiện nhiều lần, khi đó có thể dùng lũy thừa để gộp nhiều thừa số giống nhau đó lại thành một. Trong ví dụ trên, số 3 xuất hiện 2 lần và 3 2 {\displaystyle 3^{2}} là bình phương hay lũy thừa bậc 2 của 3.

Tầm quan trọng thiết yếu của số nguyên tố trong lý thuyết số và toán học nói chung có được từ định lý cơ bản của số học.[44] Định lý này phát biểu rằng bất kỳ số nguyên nào lớn hơn 1 đều có thể được viết thành tích của một hoặc nhiều số nguyên tố. Hơn nữa, tích đó là duy nhất, vì dễ thấy trong hai phân tích nguyên tố của cùng một số, các thừa số nguyên tố luôn xuất hiện với số lần bằng nhau dù thứ tự của chúng có thể khác nhau.[45] Do đó, mặc dù có nhiều cách khác nhau để tìm cách phân tích một số thông qua thuật toán phân tích số nguyên nhưng chúng đều phải cho cùng một kết quả. Số nguyên tố vì vậy còn được gọi là "khối gạch cơ bản" của số tự nhiên.[46]

Một số chứng minh về tính duy nhất của phân tích nguyên tố được dựa trên bổ đề Euclid: Nếu p {\displaystyle p} là số nguyên tố và p {\displaystyle p} chia hết một tích a b {\displaystyle ab} với a {\displaystyle a} và b {\displaystyle b} là số nguyên thì p {\displaystyle p} cũng chia hết a {\displaystyle a} hoặc b {\displaystyle b} (hoặc cả hai).[47] Ngược lại, nếu một số p {\displaystyle p} có tính chất khi chia hết một tích thì nó cũng chia hết ít nhất một thừa số trong tích, thì p {\displaystyle p} phải là số nguyên tố.[48]

Sự tồn tại vô số số nguyên tố

Có vô số số nguyên tố. Nói cách khác, dãy các số nguyên tố

2, 3, 5, 7, 11, 13, ...

không bao giờ kết thúc. Phát biểu trên còn được gọi là định lý Euclid theo tên của nhà toán học Hy Lạp cổ đại Euclid vì ông là người đầu tiên chứng minh được phát biểu này. Một số cách chứng minh khác về sự tồn tại vô số số nguyên tố bao gồm một chứng minh bằng giải tích của Euler, chứng minh của Goldbach dựa trên số Fermat,[49] chứng minh của Furstenberg từ tô pô học,[50] hay cách chứng minh đơn giản của Kummer.[51]

Chứng minh của Euclid cho thấy rằng một tập hợp hữu hạn các số nguyên tố bất kỳ là chưa hoàn thành.[52] Thật vậy, xét một tập hợp hữu hạn gồm các số nguyên tố p 1 , p 2 , … , p n {\displaystyle p_{1},p_{2},\ldots ,p_{n}} . Khi nhân các số đó với nhau và cộng thêm 1 thì ta được

N = 1 + p 1 ⋅ p 2 ⋯ p n . {\displaystyle N=1+p_{1}\cdot p_{2}\cdots p_{n}.}

Theo định lý cơ bản của số học thì N {\displaystyle N} có một phân tích nguyên tố

N = p 1 ′ ⋅ p 2 ′ ⋯ p m ′ {\displaystyle N=p'_{1}\cdot p'_{2}\cdots p'_{m}}

với một hoặc nhiều thừa số nguyên tố. N {\displaystyle N} có thể được chia hết bởi bất kỳ thừa số nào trong tích trên, nhưng lại có phần dư bằng 1 khi được chia bởi bất kỳ số nguyên tố nào trong tập hợp đã cho, nên không có thừa số nguyên tố nào của N {\displaystyle N} có trong tập hợp đó. Vì không tồn tại một tập hợp hữu hạn nào chứa tất cả các số nguyên tố nên phải có vô số số nguyên tố.

Các số được tạo ra khi cộng thêm 1 vào tích của các số nguyên tố nhỏ nhất được gọi là số Euclid.[53] Năm số Euclid đầu tiên là số nguyên tố, nhưng số Euclid thứ sáu,

1 + ( 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 ) = 30031 = 59 ⋅ 509 , {\displaystyle 1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,}

là hợp số.

Công thức số nguyên tố

Không có công thức số nguyên tố hiệu quả nào được biết đến. Chẳng hạn, không có đa thức khác hằng số nào, kể cả đa thức đa biến, chỉ cho duy nhất các giá trị nguyên tố.[54] Tuy nhiên, có một số biểu thức có thể tạo ra các giá trị nguyên tố, nhưng hiệu quả hoạt động khá thấp. Một công thức như thế được dựa trên định lý Wilson và có thể cho giá trị 2 nhiều lần, các giá trị nguyên tố khác đúng một lần.[55] Một hệ phương trình Diophantine gồm 9 biến và một tham số cũng tồn tại với tính chất: tham số đó là số nguyên tố khi và chỉ khi hệ phương trình thu được có một nghiệm trên tập hợp số tự nhiên. Tính chất đó có thể được dùng để suy ra một công thức với tính chất là tất cả các giá trị dương của nó đều là số nguyên tố.[54]

Hai công thức số nguyên tố khác đến từ định lý Mills và một định lý của Wright, cho rằng tồn tại hằng số thực A > 1 {\displaystyle A>1} và μ {\displaystyle \mu } sao cho giá trị của

⌊ A 3 n ⌋  và  ⌊ 2 ⋯ 2 2 μ ⌋ {\displaystyle \left\lfloor A^{3^{n}}\right\rfloor {\text{ và }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor }

là số nguyên tố với mọi số tự nhiên n {\displaystyle n} bất kỳ ở công thức thứ nhất và bất kỳ số lũy thừa nào trong công thức thứ hai.[56] Ở đây ⌊ ⋅ ⌋ {\displaystyle \lfloor {}\cdot {}\rfloor } là hàm sàn, số lớn nhất nhỏ hơn hoặc bằng với số được xét. Tuy nhiên, các công thức này không hữu ích vì cần phải tạo ra các số nguyên tố trước tiên để tính A {\displaystyle A} hoặc μ {\displaystyle \mu } .[54]

Các bài toán mở

Đã có nhiều giả thuyết được đặt ra liên quan đến số nguyên tố, và đa số giả thuyết như vậy không được chứng minh trong nhiều thập kỷ: cả bốn bài toán của Landau từ năm 1912 vẫn chưa có lời giải.[57] Một trong số đó là giả thuyết Goldbach cho rằng mọi số nguyên tố chẵn n {\displaystyle n} lớn hơn 2 có thể được viết thành tổng của hai số nguyên tố.[58] Tính đến năm 2014, giả thuyết này đã được xác nhận là đúng với các số lớn đến n = 4 ⋅ 10 18 {\displaystyle n=4\cdot 10^{18}} .[59] Một số giả thuyết tương tự như vậy đã được chúng minh, chẳng hạn, định lý Vinogradov cho rằng một số nguyên lẻ đủ lớn có thể được viết thành tổng của ba số nguyên tố.[60] Còn theo định lý Chen, một số nguyên tố chẵn đủ lớn có thể được biểu diễn thành tổng của một số nguyên tố và một số nửa nguyên tố (tích của hai số nguyên tố).[61] Đồng thời, một số nguyên chẵn lớn hơn 10 có thể được viết thành tổng của 6 số nguyên tố.[62] Nhánh của lý thuyết số nghiên cứu những bài toán như thế được gọi là lý thuyết cộng tính số.[63]

Một dạng bài toán khác có liên quan đến khoảng cách nguyên tố, tức là chênh lệch giữa hai số nguyên tố liên tiếp. Có thể thấy được sự tồn tại của các khoảng cách nguyên tố lớn tùy ý bằng cách chú ý rằng dãy số n ! + 2 , n ! + 3 , … , n ! + n {\displaystyle n!+2,n!+3,\dots ,n!+n} chứa n − 1 {\displaystyle n-1} hợp số với n {\displaystyle n} là số tự nhiên.[64] Tuy nhiên, khoảng cách nguyên tố lớn này bắt đầu xuất hiện sớm hơn so với thời điểm mà lập luận này đã cho.[65] Chẳng hạn, khoảng cách nguyên tố đầu tiên với độ dài bằng 8 nằm giữa hai số 89 và 97, nhỏ hơn nhiều so với 8 ! = 40320 {\displaystyle 8!=40320} .[66] Có giả thuyết cho rằng có vô số cặp số nguyên tố sinh đôi, tức là cặp số nguyên tố với chênh lệch bằng 2; đó chính là giả thuyết số nguyên tố sinh đôi. Giả thuyết Polignac phát biểu tổng quát hơn rằng với một số nguyên dương k {\displaystyle k} bất kỳ, tồn tại vô số các cặp số nguyên tố liên tiếp sai khác nhau 2 k {\displaystyle 2k} .[67] Giả thuyết Andrica,[67] giả thuyết Brocard,[68] giả thuyết Legendre [69] và giả thuyết Oppermann[68] đều cho rằng khoảng cách lớn nhất giữa các số nguyên tố từ 1 đến n {\displaystyle n} phải là xấp xỉ n {\displaystyle {\sqrt {n}}} , một kết quả được cho là suy ra từ giả thuyết Riemann, trong khi giả thuyết Cramér đặt khoảng cách lớn nhất đó bằng O ( ( log ⁡ n ) 2 ) {\displaystyle O((\log n)^{2})} .[67] Khoảng cách nguyên tố có thể được khái quát hóa thành bộ k {\displaystyle k} số nguyên tố, một bộ gồm khoảng cách giữa nhiều hơn hai số nguyên tố. Tính vô hạn và mật độ của chúng là vấn đề chính trong giả thuyết Hardy–Littlewood đầu tiên, vốn có thể được suy ra từ thuật giải heuristic rằng số nguyên tố có tính chất tương tự như một dãy số ngẫu nhiên với mật độ được cho bởi định lý số nguyên tố.[70]